翻訳と辞書 Words near each other ・ K-Rob ・ K-Rock ・ K-Rockathon ・ K-Run's Park Me In First ・ K-rupt ・ K-Salaam ・ K-series ・ K-series (TV series) ・ K-server problem ・ K-set (geometry) ・ K-Six Television ・ K-Ske Hasegawa ・ K-Slick ・ K-Solo ・ K-SOOL ・ K-approximation of k-hitting set ・ K-ary tree ・ K-B-D ・ K-ballet ・ K-band Multi-Object Spectrograph ・ K-Bar Ranch, Texas ・ K-beta ・ K-Bob's Steakhouse ・ K-box ・ K-car ・ K-Casein ・ K-CASH ・ K-cell (mathematics) ・ K-Ci & JoJo ・ K-Ci & JoJo discography Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク K-approximation of k-hitting set ： ウィキペディア英語版 K-approximation of k-hitting set In computer science, k-approximation of k-hitting set is an approximation algorithm for weighted hitting set. The input is a collection ''S'' of subsets of some universe ''T'' and a mapping ''W'' from ''T'' to non-negative numbers called the weights of the elements of ''T''. In k-hitting set the size of the sets in ''S'' cannot be larger than ''k''. That is, $\backslash forall\; i\; \backslash in\; S:\; |i|\; \backslash leq\; k$. The problem is now to pick some subset ''T''' of ''T'' such that every set in ''S'' contains some element of ''T''', and such that the total weight of all elements in ''T''' is as small as possible. ==The algorithm== For each set $j$ in ''S'' is maintained a ''price'', $p\_j$, which is initially 0. For an element ''a'' in ''T'', let ''S''(''a'') be the collection of sets from ''S'' containing ''a''. During the algorithm the following invariant is kept :$\backslash forall\; a\; \backslash in\; T:\; \backslash sum\_\; p\_j\; \backslash leq\; W(a).\backslash ,$ We say that an element, ''a'', from ''T'' is ''tight'' if $\backslash Sigma\_\; p\_j\; =\; W(a)$. The main part of the algorithm consists of a loop: As long as there is a set in ''S'' that contains an element from ''T'' which is not tight, the price of this set is increased as much as possible without violating the invariant above. When this loop exits, all sets contain some tight element. Pick all the tight elements to be the hitting set. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「K-approximation of k-hitting set」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.